import java.util.List;

/**
 * Created by L.jp
 * Description:给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
 * 注意是节点的编号而非节点的数值。
 * User: 86189
 * Date: 2022-05-23
 * Time: 12:00
 */
class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }
public class Solution {
    public ListNode oddEvenList (ListNode head) {
        //双指针，奇偶指针，奇数指针遍历到奇数节点就断开后面的指向，因为他后面是偶数节点，我们要使奇数节点连接在一起
        //所以奇数和偶数指针遍历到该节点时，就要断开与后面的指向，重新指向他们的下一个的下一个就是属于自己类的节点
        if(head==null){
            return null;
        }
        ListNode odd=head;
        ListNode even=head.next;
        //重新连接前，需要记录下偶数链表的头结点
        ListNode evenHead=even;
        //even是后面判断的，使用even来判断
        while (even!=null && even.next!=null){
            //各自断开原来与后面的指向
            odd.next=even.next;
            odd=odd.next;
            even.next=odd.next;
            even=even.next;
        }
        //连接奇偶链表
        odd.next=evenHead;
        return head;
    }
}
